function mergeSort(nums) {
  console.time("归并排序耗时");
  const N = nums.length;
  const temp = [];
  for (let sz = 1; sz < N; sz = sz + sz) {
    for (let left = 0; left < N - sz; left += sz + sz) {
      merge(
        nums,
        left,
        left + sz - 1,
        Math.min(left + sz + sz - 1, N - 1),
        temp
      );
    }
  }
  console.timeEnd("归并排序耗时");
  return nums;
}

function merge(nums, left, mid, right, temp) {
  for (let k = left; k <= right; k++) {
    temp[k] = nums[k];
  }
  let i = left;
  let j = mid + 1;
  for (let k = left; k <= right; k++) {
    if (temp[i] <= temp[j]) {
      nums[k] = temp[i];
      i++;
    } else if (temp[j] < temp[i]) {
      nums[k] = temp[j];
      j++;
    } else if (i > mid) {
      nums[k] = temp[j];
      j++;
    } else {
      nums[k] = temp[i];
      i++;
    }
  }
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

let arr = mergeSort([6, 9, 0, 4, 8, 3, 2, 7, 1, 5]);
console.log(arr);
